@InProceedings{AryaFonsMoun:2008:TrApRa,
               author = "Arya, Sunil and Fonseca, Guilherme D. da and Mount, David M.",
          affiliation = "{The Hong Kong University of Science and Technology} and 
                         {University of Maryland} and {University of Maryland}",
                title = "Tradeoffs in approximate range searching made simpler",
            booktitle = "Proceedings...",
                 year = "2008",
               editor = "Jung, Cl{\'a}udio Rosito and Walter, Marcelo",
         organization = "Brazilian Symposium on Computer Graphics and Image Processing, 21. 
                         (SIBGRAPI)",
            publisher = "IEEE Computer Society",
              address = "Los Alamitos",
             keywords = "range searching, geometric approximation, geometric data 
                         structures, computational geometry.",
             abstract = "Range searching is a fundamental problem in computational 
                         geometry. The problem involves preprocessing a set of n points in 
                         R^d into a data structure, so that it is possible to determine the 
                         subset of points lying within a given query range. In approximate 
                         range searching, a parameter eps > 0 is given, and for a given 
                         query range R the points lying within distance eps diam(R) of the 
                         range's boundary may be counted or not. In this paper we present 
                         three results related to the issue of tradeoffs in approximate 
                         range searching. First, we introduce the range sketching problem. 
                         Next, we present a space-time tradeoff for smooth convex ranges, 
                         which generalize spherical ranges. Finally, we show how to modify 
                         the previous data structure to obtain a space-time tradeoff for 
                         simplex ranges. In contrast to existing results, which are based 
                         on relatively complex data structures, all three of our results 
                         are based on simple, practical data structures.",
  conference-location = "Campo Grande, MS, Brazil",
      conference-year = "12-15 Oct. 2008",
                  doi = "10.1109/SIBGRAPI.2008.24",
                  url = "http://dx.doi.org/10.1109/SIBGRAPI.2008.24",
             language = "en",
                  ibi = "6qtX3pFwXQZG2LgkFdY/UNhNr",
                  url = "http://urlib.net/ibi/6qtX3pFwXQZG2LgkFdY/UNhNr",
           targetfile = "tradeoffs-final.pdf",
        urlaccessdate = "2024, Apr. 28"
}